使序列递增的最小交换次数(Leetcode 801)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 1.2k | 阅读时长 ≈ 5
Leetcode 801

1

题目分析

   小伙伴们看到这个题目能否立刻想到应该使用什么算法？因为用例一定能够满足条件，说明两个数组交换某些元素一定能变成两个严格单调递增的数组。假设两个数组的长度为n，那么长度为n - 1的数组，也一定是单调递增的。因此我们就可以将这个问题拆解成已知长度为n - 1的数组是单调递增的，使得长度n的数组单调递增的最小交换次数。

动态规划

DP的思想呼之欲出，第k个元素可以交换也可以不交换，用dp[k][0]表示第k个元素不交换使得前k个元素单调递增的最小交换次数。dp[k][1]表示第k个元素交换使得前k个元素单调递增的最小交换次数。

因为用例是一定成功的，所以只可能存在下面两种情况(或两种情况都满足)

  1. nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]
  2. nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]

因为长度为k - 1的数组是单调递增的，那么当条件1满足时，dp[k][0] = dp[k - 1][0]，dp[k][1] = dp[k - 1][1] + 1

解释：dp[k][0]表示第k个元素没有交换，前k个元素都递增的最小交换次数，dp[k - 1][0]表示第k - 1个元素没有交换，前k - 1个元素都递增的最小交换次数。因为满足条件1，所以两个数组仍然都还是递增的，可得dp[k][0] = dp[k - 1][0]。

dp[k][1]表示第k个元素交换了，前k个元素都递增的最小交换次数，dp[k - 1][1]表示第k - 1个元素交换了，前k - 1个元素都递增的最小交换次数。因为满足条件1，当第k个元素和第k - 1个元素都交换时，仍然满足nums1[k] > nums1[k - 1]，nums2[k] > nums2[k - 1]，可得dp[k][1] = dp[k - 1][1] + 1，加1是因为第k个元素要进行交换。

同理，当条件2满足时，dp[k][0] = dp[k - 1][1]，dp[k][1] = dp[k - 1][0] + 1

解释：dp[k][0]表示第k个元素没有交换，前k个元素都递增的最小交换次数，dp[k - 1][1]表示第k - 1个元素交换了，前k - 1个元素都递增的最小交换次数。因为满足条件2，又因为第k - 1个元素交换了，所以num1[k] > nums1[k - 1]，num2[k] > nums2k - 1，所以两个数组都是递增的，可得dp[k][0] = dp[k - 1][1]

dp[k][1]表示第k个元素交换了，前k个元素都递增的最小交换次数，dp[k - 1][0]表示第k - 1个元素没有交换，前k - 1个元素都递增的最小交换次数。因为满足条件2，又因为第k个元素交换了，所以num1[k] > nums1[k - 1]，num2[k] > nums2k - 1，所以两个数组都是递增的，可得dp[k][1] = dp[k - 1][0] + 1，加1是因为第k个元素要进行交换。

所以算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = 1;
        for (int i = 1; i < n; i++) {
            dp[i][0] = n;
            dp[i][1] = n;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                dp[i][0] = Math.min(dp[i][0], dp[i - 1][0]); 
                dp[i][1] = Math.min(dp[i][1], dp[i - 1][1] + 1);
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                dp[i][0] = Math.min(dp[i][0], dp[i - 1][1]);
                dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + 1);
            }
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}

上面同样的算法，因为每次迭代只用到前一次的两个值，因此可以使用滚动数组优化空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int dp0 = 0;
        int dp1 = 1;
        for (int i = 1; i < n; i++) {
            int newDp0 = n;
            int newDp1 = n;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                newDp0 = Math.min(newDp0, dp0);
                newDp1 = Math.min(newDp1, dp1 + 1);
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                newDp0 = Math.min(newDp0, dp1);
                newDp1 = Math.min(newDp1, dp0 + 1);
            }
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return Math.min(dp0, dp1);
    }
}

刷题总结

  本题的难度偏大，主要是如何抽象出来两个重要的条件，这也是动态规划问题的核心。

-------------本文结束感谢您的阅读-------------
0%